package algorithm.四边形不等式;

import com.alibaba.druid.sql.visitor.functions.Length;

public class SplitArrayLargestSum {

    public int splitArray(int[] nums, int k) {
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }

        int length = nums.length;
        int[][] dp = new int[length][k];
        int[][] bestSplit = new int[length][k];
        dp[0][0] = nums[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = dp[i - 1][0] + nums[i];
            bestSplit[i][0] = 0;
        }

        for (int i = 0; i < k; i++) {
            dp[0][i] = nums[0];
        }

        for (int j = 1; j < k; j++) {
            for (int i = length - 1; i > 0; i--) {

                int min = Integer.MAX_VALUE;
                int left = bestSplit[i][j - 1];
                int up = i + 1 == length? length - 1 : bestSplit[i + 1][j];
                for (int l = left; l <= up; l++) {
                    int max = Math.max(dp[l][j - 1], sum[i] - sum[l]);
                    if(max < min){
                        min = max;
                        bestSplit[i][j] = l;
                    }
                }
                dp[i][j] = min;
            }
        }

        return dp[length - 1][k -1];
    }

    public static int splitArray2(int[] arr, int k){
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            max = Math.max(max, arr[i]);
        }

        int left = max;
        int right = sum;
        while(left != right){
            int mid = (left + right) / 2;
            int num = getLeastNum(arr, mid);
            if(k < num)
                left = mid + 1;
            else{
                right = mid;
            }
        }
        return left;
    }

    public static int getLeastNum(int[] arr, int mid){
        int count = 1;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            if(sum + arr[i] > mid){
                count++;
                sum = arr[i];
            }else {
                sum += arr[i];
            }
        }
        return count;
    }



    public static void main(String[] args) {
        int[] arr = new int[]{7,2,5,10,8};
        int i = new SplitArrayLargestSum().splitArray(arr, 3);
        int i1 = splitArray2(arr, 3);
        System.out.println(i1);
        System.out.println(i);
    }
}
